package Demo1;

public class Solution {
    ListNode head = null;
    ListNode end = null;

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = null;
        ListNode endHead = null;

        //都有数值的时候
        while (list1 != null && list2 != null){
            if (list1.val < list2.val){
                if (newHead == null){
                    newHead = list1;
                    endHead = list1;
                }else{
                    endHead.next = list1;
                    endHead = endHead.next;
                }

                list1 = list1.next;
            }else{
                if (newHead == null){
                    newHead = list2;
                    endHead = list2;
                }else{
                    endHead.next = list2;
                    endHead = endHead.next;
                }

                list2 = list2.next;
            }

        }

        if (list1 == null){
            endHead.next = list2;
        }else if (list2 == null){
            endHead.next = list1;
        }

        if(endHead != null){
            endHead = endHead.next;
            endHead.next = null;

        }

        return newHead;

    }
    public ListNode addFirst(int val){
        Solution.ListNode listNode = new Solution.ListNode(val);
        if (head == null){
            head = listNode;
            end = listNode;

        }else{
            end.next = listNode;
            end = listNode;
        }

        return head;
    }
}

class Main{
    public static void main(String[] args) {
        Solution test = new Solution();
        test.addFirst(1);
        test.addFirst(2);
        Solution.ListNode ret1 = test.addFirst(4);

        Solution test2 = new Solution();
        test2.addFirst(1);
        test2.addFirst(3);
        Solution.ListNode ret2 = test2.addFirst(4);
        test.mergeTwoLists(ret1, ret2);
    }
}
